import java.util.Arrays;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("babad"));
        System.out.println(solution.longestPalindrome("cadbinbda"));
    }

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (s.charAt(0) == s.charAt(1)) {
                return s;
            }
            return Character.toString(s.charAt(0));
        }

        char[] chars = s.toCharArray();
        Rome max = new Rome(chars, 0);
        Rome temp;

        for (int i = 0; i < chars.length - 1; i++) {
            temp = new Rome(chars, i);
            if (temp.getLength() > max.getLength()) {
                max = temp;
            }

            if (chars[i] == chars[i + 1]) {
                temp = new Rome(chars, i, i + 1);
                if (temp.getLength() > max.getLength()) {
                    max = temp;
                }
            }
        }

        char[] result = Arrays.copyOfRange(chars, max.start, max.end + 1);
        return new String(result);
    }

    private class Rome {
        int start;
        int end;

        Rome(char[] arr, int mid) {
            start = mid - 1;
            end = mid + 1;
            while (start >= 0 && end < arr.length) {
                if (arr[start] == arr[end]) {
                    start--;
                    end++;
                } else {
                    break;
                }
            }
            start++;
            end--;
        }

        Rome(char[] arr, int mid1, int mid2) {
            start = mid1 - 1;
            end = mid2 + 1;
            while (start >= 0 && end < arr.length) {
                if (arr[start] == arr[end]) {
                    start--;
                    end++;
                } else {
                    break;
                }
            }
            start++;
            end--;
        }

        int getLength() {
            return end - start + 1;
        }
    }

}